/*
 * @Author: liruo liruo_hrh@163.com
 * @Date: 2022-11-27 13:29:31
 * @LastEditors: liruo liruo_hrh@163.com
 * @LastEditTime: 2022-11-27 13:34:09
 * @FilePath: \dahua-data-struct\me\tree\BSTree.hpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
#ifndef BINARY_TREE_H
#define BINARY_TREE_H
#include <iostream>
#include "statck_byarr.hpp"
using namespace std;
template<class T>
class TreeNode
{
public:
    TreeNode *left;
    TreeNode *right;
    TreeNode(T data, TreeNode *left = nullptr, TreeNode *right = nullptr):data(data),left(left),right(right){}
    ~TreeNode(){
        left = nullptr;
        right = nullptr;
    }
    T data;
};
template<class T>
class BSTree
{
public:
    BSTree(){}
    ~BSTree(){
        root = nullptr;
    }

    void add(int data){
        if(root == nullptr){
            root = new TreeNode<T>(data);
            return;
        }
        TreeNode<T>* p = root;
        while(true){
            if(data > p->data){
                if(p->right == nullptr){
                    p->right = new TreeNode<T>(data);
                    return;
                }
                p = p->right;
            }else{
                if(p->left == nullptr){
                    p->left = new TreeNode<T>(data);
                    return;
                }
                p = p->left;
            }
        }
    }
    void traverse_pre_recursion(){
        cout<<"[";
        traverse_pre_recursion(root);
        cout<<"]\n";
    }
    void traverse_pre_stack(){
        TreeNode<T> *p = root;
        Stack<TreeNode<T>*> stack;
        cout<<"[";
        while(p != nullptr || !stack.isEmpty()){
            while(p != nullptr){
                cout<<p->data<<" ";
                stack.push(p);
                p = p->left;
            }
            p = stack.pop();
            p = p->right;
        }
        cout<<"]\n";
    }
    void traverse_in_recursion(){
        cout<<"[";
        traverse_in_recursion(root);
        cout<<"]\n";
    }
    void traverse_in_stack(){
        TreeNode<T> *p = root;
        Stack<TreeNode<T>*> stack;
        cout<<"[";
        while(p != nullptr || !stack.isEmpty()){
            while(p != nullptr){
                stack.push(p);
                p = p->left;
            }
            p = stack.pop();
            cout<<p->data<<" ";
            p = p->right;
        }
        cout<<"]\n";
    }
    void traverse_post_recursion(){
        cout<<"[";
        traverse_post_recursion(root);
        cout<<"]\n";
    }
    void traverse_post_stack(){
        TreeNode<T> *p = root;
        Stack<TreeNode<T>*> stack;
        Stack<TreeNode<T>*> repeatStack;
        cout<<"[";
        //preGet记录前一个获取的节点
        TreeNode<T> * preGetNode;
        while(p != nullptr || !stack.isEmpty()){
            while(p != nullptr){
                stack.push(p);
                p = p->left;
            }
            p = stack.pop();
            //当从right子树回到root,即p=root,p.right != null
            //因为已经进入过right子树了，且前一个获取的节点preGetNode就是p.right
            //因此如果p->right == nullptr的情况下preGetNode==p->right 就表示进入过right子树，直接打印p这个root节点，再往上回溯
            if(p->right == nullptr || p->right == preGetNode){
                cout<<p->data<<" ";
                preGetNode = p;
                p = nullptr;
            }else{
                stack.push(p);
                p = p->right;
            }
        }
        cout<<"]\n";
    }
private:
    void traverse_pre_recursion(TreeNode<T>* node){
        if(node == nullptr){
            return;
        }
        cout<<node->data<<" ";
        traverse_pre_recursion(node->left);
        traverse_pre_recursion(node->right);
    }
    void traverse_in_recursion(TreeNode<T>* node){
        if(node == nullptr){
            return;
        }
        traverse_in_recursion(node->left);
        cout<<node->data<<" ";
        traverse_in_recursion(node->right);
    }
    void traverse_post_recursion(TreeNode<T>* node){
        if(node == nullptr){
            return;
        }
        traverse_post_recursion(node->left);
        traverse_post_recursion(node->right);
        cout<<node->data<<" ";
    }
    TreeNode<T> *root = nullptr;
};

#endif // BINARY_TREE_H